home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group93b.txt / 000024_icon-group-sender _Sun Apr 25 22:08:38 1993.msg < prev    next >
Internet Message Format  |  1993-06-16  |  6KB
  1. Received: by cheltenham.cs.arizona.edu; Mon, 26 Apr 1993 04:31:36 MST
  2. Message-Id: <9304260508.AA21290@internal.apple.com>
  3. Date: Sun, 25 Apr 1993 22:08:38 -0800
  4. To: icon-group@cs.arizona.edu
  5. From: nevin@apple.com (Nevin ":-]" Liber)
  6. X-Sender: nevin@130.43.2.2
  7. Subject: Re: Is this passable code?
  8. Cc: glauber@david.wheaton.edu (Glauber Ribeiro)
  9. Status: R
  10. Errors-To: icon-group-errors@cs.arizona.edu
  11.  
  12. >I started using Icon recently, and am impressed with the
  13. >power of the language. But, since i'm learning on my own and
  14. >don't have experience with Icon, i don't know if i'm doing
  15. >things right. Recently i wrote a short program to find
  16. >anagrams (yeah...) using the unix dictionary. I'd appreciate
  17. >any comments/suggestions/flames, etc about my programming
  18. >style and the Icon way.
  19.  
  20. I did think of a different (simpler, I believe) way of implementing the
  21. anagram algorithm, using sets.  I don't know if it's better or worse, but
  22. it does illustrate my particular style for programming in Icon.  Here it
  23. is, along with an explanation of some of my stylistic choices:
  24.  
  25.  
  26. # look up anagrams of all the command line arguments in /usr/dict/words
  27.  
  28.  
  29. procedure main(LArguments)
  30.  
  31. local   SAnagrams
  32. local   fWords
  33. local   sWord
  34.  
  35. SAnagrams := set()
  36.  
  37. every insert(SAnagrams, Permute(map(!LArguments)))
  38.  
  39. fWords := open("/usr/dict/words") |
  40.         stop("Cannot open /usr/dict/words for reading; aborting.")
  41.  
  42. while sWord := read(fWords) do {
  43.         if member(SAnagrams, map(sWord)) then write(sWord)
  44. }
  45.  
  46. close(fWords)
  47.  
  48.  
  49. end
  50.  
  51.  
  52. procedure Permute(sString)
  53.  
  54. local   iPos
  55.  
  56. if 0 = *sString then return sString
  57.  
  58. suspend sString[iPos := 1 to *sString] ||
  59.         Permute(sString[1:iPos] || sString[iPos+1:0])
  60.  
  61. end
  62.  
  63.  
  64.  
  65. Variable conventions:  In my code, the first letter of each variable
  66. identifies what kind of value it contains, following the convention on the
  67. first page of the Reference Manual in the Icon book.  In this program, L
  68. stands for list, S for set, f for file, s for string, and i for integer.  I
  69. also try and give full names to variables to make the code more readable
  70. and understandable.  I also capitalise the first letter of each word (an
  71. Apple convention for code, which I like much, much better than using
  72. underscores), as well as starting all of my functions with a capital
  73. letter.  I tend to declare all of my local variables, so that icont -u can
  74. catch an inadvertent spelling errors.
  75.  
  76. Permute():  This is a recursive generator which produces all possible
  77. permutations of its argument.  I tend to let the caller (in this case,
  78. main()) build the container structure (a set) instead of the callee because
  79. in many cases the results of a generator can be used directly without
  80. having to build a large data structure in memory.
  81.  
  82. Important points about main():
  83.  
  84. every insert(SAnagrams, Permute(map(!LArguments))):  "every" generates all
  85. possible values for the insert(...) expression.  Let's analyse this from
  86. inside to out:
  87.  
  88. every !LArguments:  this produces all the members of list LArguments, in
  89. order.  In this case, this produces strings of all the command line
  90. arguments.  If there are no arguments, it fails; failure is inherited by
  91. the rest of the expression, and the set SAnagrams remains empty.
  92.  
  93. every map(!LArguments):  When I use map() with it's default arguments for
  94. s2 (source mapping string) and s3 (destination mapping string), I think of
  95. it as "removing" the caseness of its argument; I don't really care if it
  96. converts it to all uppercase or all lowercase.
  97.  
  98. every Permute(map(!LArguments)):  This produces all the possible "caseless"
  99. permutations of all the command line arguments.  Although this is logically
  100. equivalent to every map(Permute(!LArguments)), I chose to put it inside of
  101. Permute(...) because it is more efficient to call it once per command line
  102. argument than to call it for each permutation.
  103.  
  104. every insert(SAnagrams, Permute(map(!LArguments))):  This produces a set of
  105. all the possible "caseless" permutations of all the command line arguments.
  106.  If there are duplicate permutations (if a given letter appears more than
  107. once in a word, there will be duplicate permutations), they are
  108. automatically discarded since we are using a set data type.
  109.  
  110. fWords := open("/usr/dict/words") |
  111.         stop("Cannot open /usr/dict/words for reading; aborting."):
  112. I prefer to use alternation (|) instead of an if statement.  I think of the
  113. open() as the normal expected case, and the stop() clause as the
  114. "exception".
  115.  
  116. if member(SAnagrams, map(sWord)) then write(sWord):  Again, I do a
  117. map(sWord) to remove the caseness of SWord so I can do a caseless
  118. comparison.  If it's in the set of possible anagrams, I write out the word,
  119. preserving the case it has in /usr/dict/words.
  120.  
  121.  
  122. Variations on this algorithm:  There are 24259 words in /usr/dict/words on
  123. my Unix machine.  If I was expecting to process many words with 8 or more
  124. unique letters (8! = 40320 permutations), I would have approached this a
  125. little differently.  I would have read /usr/dict/words into a set (or a
  126. table, if I thought that preserving case was important), and do something
  127. like [note:  if you want to preserve case, it's actually a little harder
  128. than this.  The algorithm below ignores words in /usr/dict/words that only
  129. differ by case, and it probably shouldn't]:
  130.  
  131.  
  132.  
  133. procedure main(LArguments)
  134.  
  135. local   TWords
  136. local   fWords
  137. local   sWord
  138.  
  139. TWords := table()
  140.  
  141. fWords := open("/usr/dict/words") |
  142.         stop("Cannot open /usr/dict/words for reading; aborting.")
  143.  
  144. while sWord := read(fWords) do TWords[map(sWord)] := sWord
  145.  
  146. close(fWords)
  147.  
  148.  
  149. every write(\TWords[Permute(map(!LArguments))])
  150.  
  151. end
  152.  
  153.  
  154.  
  155. I would probably even come up with a heuristic that analyses LArguments and
  156. determines which of the two above variations to call to do the work.
  157.  
  158.  
  159. I hope this is what you were looking for.  I can't believe I wrote this
  160. much on a 20 line algorithm. :-)  Comments are appreciated.
  161. ___
  162. NEVIN ":-)" LIBER,      Blue Meanie, Macintosh System Software
  163.  email:     nevin@apple.com        paper:  Apple Computer, Inc.
  164.  voice:     (408) 974-MIX1                 2 Infinite Loop, MS: 302-4Q
  165.  AppleLink: BADENOV                        Cupertino, CA 95014
  166.  
  167.